package 力扣.双指针.最长区间;

import java.util.HashMap;
import java.util.Map;

public class 最大子数组之和为k_li911 {
    /**
     * 给一个数组nums和目标值k，找到数组中最长的子数组，使其中的元素和为k。如果没有，则返回0。
     * 数组之和保证在32位有符号整型数的范围内
     *
     * 样例1
     *
     * 输入: nums = [1, -1, 5, -2, 3], k = 3
     * 输出: 4
     * 解释:
     * 子数组[1, -1, 5, -2]的和为3，且长度最大
     *
     * 样例2
     *
     * 输入: nums = [-2, -1, 2, 1], k = 1
     * 输出: 2
     * 解释:
     * 子数组[-1, 2]的和为1，且长度最大
     */

    /**
     * 记忆化前缀和
     * @param nums
     * @param k
     * @return
     */
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(); // sum -> id
        map.put(0, -1);
        int maxLen = 0;
        for (int i = 0, sum = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                maxLen = Math.max(maxLen, i - map.get(sum - k));
            } else {
                map.putIfAbsent(sum, i);//如果存在重复的key,那么putIfAbsent不会放入值
            }
        }
        return maxLen;
    }



}
